﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BinaryTree
{
    /// <summary>
    /// 中序遍历
    /// </summary>
    class MiddleOrder
    {
        /// <summary>
        /// 递归
        /// </summary>
        /// <param name="tree"></param>
        public static void InOrder(CreatTree.Tree tree)
        {
            if (tree == null) return;
            InOrder(tree.Left);
            Console.Write(tree.Value);
            InOrder(tree.Right);
        }
        /// <summary>
        /// 非递归
        /// </summary>
        /// <param name="tree"></param>
        public static void InOrderNoRecursion(CreatTree.Tree tree)
        {
            if (tree == null) return;
            Stack<CreatTree.Tree> stack = new Stack<CreatTree.Tree>();
            CreatTree.Tree node = tree;
            while (node != null || stack.Any())
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.Left;
                }
                else
                {
                    var item = stack.Pop();
                    Console.Write(item.Value);
                    node = item.Right;
                }
            }
        }
    }
}
